# forward-compat boilerplate
from __future__ import absolute_import
from __future__ import with_statement
__metaclass__ = type

import os
import re
import sys
import time
import string
import inspect
import threading
import functools
from collections import defaultdict


if sys.platform == 'win32':
    timer = time.clock
else:
    timer = time.time


builtin_property = property


# python language utils
#######################

def classname(obj):
    if not isinstance(obj, type):
        obj = type(obj)
    return obj.__module__ + '.' + obj.__name__


class classproperty:
    def __init__(self, fget):
        self.fget = fget
    def __get__(self, obj, type):
        return self.fget(type)


class classinstancemethod:
    def __init__(self, func):
        self.func = func
    def __get__(self, instance, owner):
        import new
        if instance is None:
            return new.instancemethod(self.func, owner, owner.__class__)
        else:
            return new.instancemethod(self.func, instance, owner)


class classinstanceproperty:
    def __init__(self, fget):
        self.fget = fget
    def __get__(self, instance, owner):
        return self.fget(owner, instance)


def getvar(name, offset=1):
    f = sys._getframe(offset)
    while f:
        if name in f.f_locals:
            return f.f_locals[name]
        f = f.f_back
    raise NameError('Dynamic variable %s not found' % name)


def reprargs(*x, **y):
    x = ', '.join(map(repr, x))
    y = ', '.join('%s=%r'%p for p in y.iteritems())
    return ', '.join((x and [x] or []) + (y and [y] or []))


class dynamic_var_getter:
    def __getattr__(self, name):
        return getvar(name, 2)

dynamic = dynamic_var_getter()


def wrapwith(wrapper):
    def decorate(wrapped):
        @functools.wraps(wrapped)
        def actual(*args, **kw):
            return wrapper(wrapped(*args, **kw))
        return actual
    return decorate




def yieldlist(f):
    @functools.wraps(f)
    def x(*args, **kw):
        return list(f(*args, **kw))
    return x




class synchronized:

    def __init__(self, func):
        self.lock = threading.Lock()
        self.func = func

    def __get__(self, obj, type):
        return obj is None and self or self.bound(obj)

    def bound(self, __obj):
        @functools.wraps(self.func)
        def bound(*__args, **__kw):
            with self.lock:
                return self.func(__obj, *__args, **__kw)
        bound.__name__ += ' (synchronized)'
        return bound


# UNUSED
class synchronized_property:
    def __init__(self, value=None):
        self.value = value
        self.lock = threading.Lock()
    def __get__(self, type, obj):
        return self.value
    def __set__(self, obj, value):
        with self.lock:
            self.value = value


def normalize_path(f=None):
    mf = sys.modules['__main__'].__file__
    mp = os.path.dirname(os.path.realpath(mf))
    sys.path[:] = [p for p in sys.path if p != mp]


def property(fget=None, fset=None, fdel=None, doc=None):
    # if function takes a parameter, assume it is 'self'
    # and usethis is a simple accessor property
    if inspect.getargspec(fget)[0]:
        return builtin_property(fget, fset=fset, fdel=fdel,
                                doc=doc or inspect.getdoc(fget))
    assert not fset and not fdel
    return fancy_property(fget)

def fancy_property(func):
    # else function takes no parameters and defines
    # fget, fset, fdel in local scope
    # do some hackery to get the fget, fset, fdel
    funcs = set(['fget', 'fset', 'fdel'])
    import new
    kw = {}
    code = func.func_code
    globs = func.func_globals
    kw = dict((c.co_name, new.function(c, globs))
               for c in code.co_consts
               if type(c) is type(code) and c.co_name in funcs)
    kw['doc'] = inspect.getdoc(func)
    return builtin_property(**kw)


def topsort(pairs):

    adjacencies = {}
    incount = {}

    for src, dst in pairs:
        adjacencies.setdefault(src, [])
        adjacencies.setdefault(dst, [])
        adjacencies[src].append(dst)
        incount.setdefault(src, 0)
        incount.setdefault(dst, 0)
        incount[dst] += 1

    roots = [x for x in adjacencies if not incount[x]]
    out = []
    while roots:
        this = roots.pop()
        for node in adjacencies[this]:
            out.append((this, node))
            incount[node] -= 1
            if not incount[node]:
                roots.append(node)
        del adjacencies[this]
    return not adjacencies and out or []




class LazyAttributeError(Exception):
    '''An exception for lazy attributes so that AttributeErrors thrown
    don't get caught by getattr() trickery'''


class lazyattr:
    def __init__(self, factory):
        self.factory = factory
        name = getattr(factory, '__name__', None)
        if not name or name == '<lambda>':
            name = str(factory)
        self.name = '____lazy____' + name
        self.hasparam = inspect.getargspec(factory)[0]
    def __get__(self, obj, type):
        if obj is None:
            return self
        try:
            x = getattr(obj, self.name)
        except AttributeError:
            try:
                if self.hasparam:
                    x = self.factory(obj)
                else:
                    x = self.factory()
            except AttributeError, e:
                raise LazyAttributeError, LazyAttributeError(e), sys.exc_info()[2]
            setattr(obj, self.name, x)
        return x
    def __set__(self, obj, v):
        setattr(obj, self.name, v)


def listgen(f):
    @functools.wraps(f)
    def g(*args, **kw):
        return list(f(*args, **kw))
    return g

def newdict(*ds, **kw):
    return dict(sum([d.items() for d in ds], []) + kw.items())


class dictobject(dict):
    def __getattr__(self, k):
        return self[k]
    def __setattr__(self, k, v):
        self[k] = v


class defaultdictobject(defaultdict):
    def __getattr__(self, k):
        return self[k]
    def __setattr__(self, k, v):
        self[k] = v


class varsobject(defaultdictobject):
    def __init__(self, default=lambda:None):
        defaultdictobject.__init__(self, default)
    def __repr__(self):
        return '{' + ', '.join('%s: %r' % x for x in self.items()) + '}'

symbol = None
class symbol:
    def __repr__(self):
        return '<symbol %s>' % self.name
    def __str__(self):
        return self.name
    def __init__(self, name):
        self.name = name
    def __eq__(self, other):
        return self is other
    class __metaclass__(type):
        def __new__(Class, name, bases, members):
            if symbol:
                return symbol(name)
            return type.__new__(Class, name, bases, members)


def install_object(obj, module, name=None, overwrite=False):
    mod = sys.modules[module]
    if name is None:
        name = 'anonymous_' + uniqid()
    if hasattr(mod, name) and not overwrite:
        raise AttributeError('Not overwriting %s.%s' % (module, name))
    obj.__name__ = name
    obj.__module__ = module
    setattr(mod, name, obj)


def maptree(visit, tree, iter=iter):
    for node in iter(tree):
        maptree(visit, node, iter)
    visit(tree)

def doall(fs):
    def ff(*args, **kw):
        for f in fs:
            f(*args, **kw)
    return ff


def rollover_midnight(ts, refts, threshold=None):
    import datetime
    if ts < refts - (threshold or datetime.timedelta(0)):
        return ts + datetime.timedelta(1)
    return ts


def format_datetime(dt):
    return '%s, %d %s' % (dt.strftime('%a'), dt.day,
                          dt.strftime('%y %H:%M:%S GMT%z'))

#
# debugging utils
##################

def extract_tb(tb, limit=None):
    if limit is None:
        if hasattr(sys, 'tracebacklimit'):
            limit = sys.tracebacklimit
    list = []
    n = 0
    while tb is not None and (limit is None or n < limit):
        f = tb.tb_frame
        list.append(dict(lineno = tb.tb_lineno,
                         filename = f.f_code.co_filename,
                         name = f.f_code.co_name,
                         locals = f.f_locals,
                         modname = f.f_globals.get('__name__', None)))
        tb = tb.tb_next
        n += 1
    return list

def extract_stack(f=None, limit=None):
    if f is None:
        try:
            raise ZeroDivisionError
        except ZeroDivisionError:
            f = sys.exc_info()[2].tb_frame.f_back
    if limit is None:
        if hasattr(sys, 'tracebacklimit'):
            limit = sys.tracebacklimit
    list = []
    n = 0
    while f is not None and (limit is None or n < limit):
        list.append(dict(lineno = f.f_lineno,
                         filename = f.f_code.co_filename,
                         name = f.f_code.co_name,
                         locals = f.f_locals,
                         modname = f.f_globals.get('__name__', None)))
        f = f.f_back
        n += 1
    list.reverse()
    return list

def format_list(frames, color=False):
    import linecache
    list = []
    fmt = '  %s:%d %s\n'
    g = r = y = lambda x:x
    if color:
        from fenton.console import colors
        g = colors.Green
        r = colors.Red
        y = colors.Yellow
    for f in frames:
        item = '  %s:%s %s\n' % (g(f['modname']), r(f['lineno']), y(f['name']))
        line = linecache.getline(f['filename'], f['lineno'])
        if line:
            item += '    %s\n' % line.strip()
        list.append(item)
    return list

def color_tb(tb, limit=None):
    return format_list(extract_tb(tb, limit), color=True)

def color_stack(f=None, limit=None):
    return format_list(extract_stack(f, limit), color=True)

def formattable(data, n):
    fs = []
    for col in range(n):
        fs.append('%%-%ds' % max(len(str(t[col])) for t in data))

    for row in data:
        line = []
        for col in range(n):
            line.append(fs[col] % row[col])
        yield line


# inspection

def _getmethod(frame):
    f = frame
    c = frame.f_code
    if not c.co_varnames:
        # can't be method, no arguments!
        return None

    selfname = c.co_varnames[0]
    if selfname in f.f_locals:
        self = f.f_locals[selfname]
    elif 'self' in f.f_locals:
        self = f.f_locals['self']
    else:
        # can't find 'self'
        return None

    if not hasattr(self, '__class__'):
        # first arg not an instance
        return None
    if isinstance(self, type):
        Class = self
    else:
        Class = self.__class__
    for O in Class.__mro__:
        for name in O.__dict__:
            try:
                attr = getattr(O, name)
            except:
                continue
            if type(attr) is builtin_property:
                for func in 'fget', 'fset', 'fdel':
                    func = getattr(attr, func)
                    if func:
                        func = getattr(func, 'im_func', func)
                        if func.func_code is c:
                            return O, self, func, name
            func = getattr(attr, 'im_func', attr)
            if getattr(func, 'func_code', None) is c:
                return O, self, attr, name
    return None


def frameinfo(f=None):
    if f is None:
        f = sys._getframe(1)
    c = f.f_code
    stuff = _getmethod(f)
    if stuff:
        Class, self, func, attr = stuff
        modname = Class.__module__
    else:
        Class = self = func = attr = None
        modname = f.f_globals.get('__name__')

    return {'class': Class,
            'self': self,
            'module': modname,
            'file': c.co_filename,
            'line': f.f_lineno,
            'function': func and func.func_name or c.co_name,
            'method': attr}


def getcaller(offset=0):
    f = sys._getframe(2+offset)
    return frameinfo(f)


_callers = {}


def attrwatcher(T):
    loc = threading.local()
    #_callers.append((T, callers))
    def getattribute(self, name):
        if not getattr(loc, 'stop', False):
            loc.stop = True
            fr = getcaller()
            cl = fr['class'] and (fr['class'].__name__ + '.') or ''
            attr = cl + (fr['method'] or fr['function'] or '?')
            k = (T+'.'+name, attr, fr['file'])
            if k not in _callers:
                _callers[k] = fr
            loc.stop = False
        return object.__getattribute__(self, name)
    return getattribute


def printcallers():
    if not _callers:
        return
    strip = os.path.abspath(os.path.dirname(os.path.dirname(__file__))) + '/'
    data = []
    for k in sorted(_callers):
        fr = _callers[k]
        name, attr, fn = k
        fn = fn.replace(strip, '')
        if 'site-packages' in fn:
            fn = fn[fn.index('site-packages')+14:]
        elif 'mako.py' in fn:
            fn = os.path.basename(fn)
        data.append((name, attr, fn, fr['line']))
    print '\n'
    for row in formattable(data, 4):
        print ' '.join(row)
    print '\n'


# misc bits and bobs

def uint(x):
    return x & 0xffffffff

def byteswap(x):
    if x >= 0xffffffff-1:
        return None
    import struct
    return struct.unpack('<I', struct.pack('>I', x))[0]


class sequence:
    def __init__(self, start):
        self.start = start
        self.next = None
    def __call__(self):
        if not self.next:
            import itertools
            start = self.start
            if callable(start):
                start = start()
            self.next = itertools.count(start).next
        return self.next()

def camel(t):
    return ''.join(t.replace('_', '\x00').title().split('\x00'))

recamel = camel

#_camel_re = re.compile('^([A-Z]+[a-z]*)')
_camel_re = re.compile('^([A-Z][a-z0-9_]*)')
def decamel(s, sep='_'):
    'FooBar -> foo_bar, NotANumber -> not_a_number'
    out = []
    while True:
        m = _camel_re.match(s)
        if not m: break
        out.append(m.groups()[0].lower())
        s = s.replace(m.groups()[0], '', 1)
    return out and sep.join(out) or s

def escape(v):
    import cgi
    if v is None:
        return u''
    if not isinstance(v, basestring):
        v = unicode(v)
    return unicode(cgi.escape(v, True))

def scalar(x):
    if len(x) == 1:
        return x[0]
    return tuple(x)


# some useful functions

def identity(x):
    'Always return x'
    return x

def void(x):
    'Always return None'
    return None

def traverse(x, path):
    'if path is a.b.c, return x.a.b.c'
    return reduce(getattr, path.split('.'), x)

def traverser(path):
    '''
    Given an attribute path (a.b.c)
    return a function that traverses the path
    (eg, x.a.b.c)
    '''
    return lambda x: traverse(x, path)

def alias(path):
    return builtin_property(traverser(path))

def noimpl(f):
    @functools.wraps(f)
    def throw(*a, **k):
        raise NotImplementedError(f.__name__)
    return throw

def int_to_base(n, alphabet):
    base = len(alphabet)
    q = abs(n)
    out = []
    while True:
        q, r = divmod(q, base)
        out.append(alphabet[r])
        if q == 0:
            break
    neg = n < 0 and '-' or ''
    return neg + ''.join(reversed(out))

def base_to_int(s, alphabet):
    pol = 1
    if s and s[0] == '-':
        s = s[1:]
        pol = -1
    if not s:
        raise TypeError('empty string')
    i=0
    n = alphabet.index(s[i])
    base = len(alphabet)
    while s[i+1:]:
        r = s[i+1:i+2]
        n = n * base + alphabet.index(r)
        i += 1
    return n * pol

_B62 = string.digits + string.uppercase + string.lowercase
_B36 = string.digits + string.uppercase

def to_base62(n, alphabet=_B62):
    return int_to_base(n, alphabet)

def from_base62(s, alphabet=_B62):
    return base_to_int(s, alphabet)

def to_base36(n, alphabet=_B36):
    return int_to_base(n, alphabet)

def from_base36(s, alphabet=_B36):
    return base_to_int(s, alphabet)

_suffixes = 'kmgtpezy'
_bytere = re.compile('^(\d+)([%s]b?)?$' % _suffixes)

def bytesize(s, suffixes=_suffixes, r=_bytere):
    m = r.match(s.strip().lower())
    if not m:
        return None
    a, b = m.groups()
    a = int(a)
    if not b:
        return a
    i = suffixes.index(b[:1])
    return a * 1024 ** (i+1)

_ENC_ALTCHARS='+/'
_WEB_ALTCHARS='._'
_STRIP_RE=re.compile('=*$')

def enc64(s, alt=_ENC_ALTCHARS, strip=False):
    import base64
    ret = base64.b64encode(s, alt)
    if not strip:
        return ret
    return _STRIP_RE.sub('', ret)

def dec64(s, alt=_ENC_ALTCHARS, pad=False):
    import base64
    if pad:
        s = s+((4-len(s))%4)*'='
    return base64.b64decode(s, alt)

def uniqid(size=16):
    chars = os.urandom(size)
    # chars = uuid.uuid4().bytes
    # chars = ''.join(chr(random.randint(0, 256)) for _ in range(size))
    return enc64(chars, _WEB_ALTCHARS, strip=True)


# UNDEFINED: an object that cannot be used, except as a placeholder

class Undefined(Exception):
    pass

def throws(name):
    def throw(*x,**y):
        raise Undefined
    throw.__name__ = name
    return throw

@apply
def undefined():

    def throw(*a, **k):
        raise Undefined

    class undefmeta(type):
        def __new__(Self, name, bases, attrs, sentinel=None):
            if sentinel is None:
                raise Undefined
            return type.__new__(Self, name, bases, attrs)
        def __init__(self, name, bases, attrs, sentinel=None):
            if sentinel is None:
                raise Undefined
        def __repr__(self):
            return 'UNDEFINED'


    throwers = [
        'getattribute',
        'abs',
        'add',
        'and',
        'base',
        'bases',
        'basicsize',
        'call',
        'class',
        'cmp',
        'coerce',
        'contains',
        'delattr',
        'delete',
        'delitem',
        'delslice',
        'dict',
        'dictoffset',
        'div',
        'divmod',
        'doc',
        'enter',
        'eq',
        'exit',
        'flags',
        'float',
        'floordiv',
        'ge',
        'get',
        'getformat',
        'getitem',
        'getnewargs',
        'getslice',
        'gt',
        'hash',
        'hex',
        'iadd',
        'iand',
        'idiv',
        'ifloordiv',
        'ilshift',
        'imod',
        'imul',
        'index',
        'int',
        'invert',
        'ior',
        'ipow',
        'irshift',
        'isub',
        'itemsize',
        'iter',
        'itruediv',
        'ixor',
        'le',
        'len',
        'long',
        'lshift',
        'lt',
        'mod',
        'module',
        'mro',
        'mul',
        'name',
        'ne',
        'neg',
        'nonzero',
        'objclass',
        'oct',
        'or',
        'pos',
        'pow',
        'radd',
        'rand',
        'rdiv',
        'rdivmod',
        'reduce',
        'reduce_ex',
        'reversed',
        'rfloordiv',
        'rlshift',
        'rmod',
        'rmul',
        'ror',
        'rpow',
        'rrshift',
        'rshift',
        'rsub',
        'rtruediv',
        'rxor',
        'self',
        'set',
        'setattr',
        'setformat',
        'setitem',
        'setslice',
        'str',
        'sub',
        'subclasses',
        'truediv',
        'weakref',
        'weakrefoffset',
        'xor',
        ]

    throwers = ('__%s__' % k for k in throwers)
    throwers = dict((k, throws(k)) for k in throwers)

    return undefmeta('undefined', (object,), throwers, 1)



def get_modattr(impname):
    impname = impname.split('.')
    module = '.'.join(impname[:-1])
    name = impname[-1]
    __import__(module)
    mod = sys.modules[module]
    return mod, name


class fileiter:
    def __init__(self, it):
        self.it = it
        self.buf = []
        self.readcount = 0

    def read(self, size=None):
        if size is None:
            return ''.join(self.it)
        for line in self.it:
            if self.readcount > size:
                return self.flush(size)
            self.consume(line)
        return self.flush(size)

    def consume(self, line):
        self.buf.append(line)
        self.readcount += len(line)

    def flush(self, size):
        out = ''.join(self.buf)
        self.buf = [out[size:]]
        self.readcount = len(self.buf[0])
        return out[:size]


#################################################################
##                                                             ##
##                  unused stuff follows                       ##
##                                                             ##
#################################################################



def get_module(qualname, throw_missing=True, create=False):
    if create:
        throw_missing=False
    if qualname in sys.modules:
        return sys.modules[qualname]
    try:
        __import__(qualname)
    except ImportError:
        # traceback of length 1 indicates module not found
        # rather than an import error raised inside module
        if throw_missing or sys.exc_info()[2].tb_next is not None:
            raise
        if not create:
            return None
        import imp
        module = imp.new_module(qualname)
        sys.modules[qualname] = module
    return sys.modules[qualname]



def func():
    return This().attr()

frames = []
class This:
    def __getattribute__(self, name):
        frames.append(sys._getframe(1))
        frames.append(getcaller())
        return super(This, self).__getattribute__(name)
    def attr(self):
        pass

class Base:
    def basemeth(self):
        return This().attr()

class Other(Base):
    def instmeth(self):
        return This().attr()
    @classmethod
    def clmeth(self):
        return This().attr()
    @staticmethod
    def stmeth():
        return This().attr()


def testcaller():
    s = '''
    func()
    Other().basemeth()
    Other().instmeth()
    Other().clmeth()
    Other.clmeth()
    Other.stmeth()
    '''
    for line in s.strip().split():
        eval(line)
        print line, frames[-1]

